package org.czl.leetCode3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class l699 {
    public static void main(String[] args) {
        //[1,2],[2,3],[6,1]
        System.out.println(fallingSquares(new int[][]{{6, 1}, {9, 2}, {2, 4}}));
    }
    //维护区间最值 同时范围重置和范围重置的线段树
    static int[] max;
    static int[] up;
    static boolean[] check;
    static int[] arr = new int[2005];
   static public List<Integer> fallingSquares(int[][] positions) {
        int size = 0;
        for(int[] position : positions){
            arr[size++] = position[0];
            arr[size++] = position[0] + position[1] - 1;
        }
        Arrays.sort(arr,0 ,size);
        //去重
        int n = 1;
        for(int i = 1; i <= size;i++){
            if(arr[n] != arr[i]){
                arr[++n] = arr[i];
            }
        }
        //--------------------
        max = new int[n * 4];
        up = new int[n * 4];
        check = new boolean[n * 4];
        //biuld(0, n - 1, 1);
        List<Integer> ans = new ArrayList<>();
        for(int[] p : positions){
            int l = rank(0, n - 1, p[0]);
            int r = rank(0, n - 1, p[0] + p[1] - 1);
            int max = query(l, r, 0, n - 1, 1);
            update(l,r,max + p[1],0 , n - 1, 1);
            ans.add(query(0,n - 1, 0, n - 1, 1));
        }
        return ans;
    }

    static int rank(int left, int right, int goal){
        int ans = 0;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(arr[mid] >= goal){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }

        }
        return ans;
    }


    static void biuld(int left, int right, int i){
        if(left == right){
            max[i] = arr[left];
        }else{
            int mid = (left + right) / 2;
            biuld(left, mid, i << 1);
            biuld(mid + 1, right, i << 1 | 1);
            max[i] = Math.max(max[i << 1], max[i << 1 | 1]);
        }
    }

    static void down(int i, int ln, int rn){
        if(check[i]){//up等于true表示当前有懒信息
            lazy(i << 1, up[i]);
            lazy(i << 1 | 1, up[i]);
            check[i] = false;
        }
    }
    static void lazy(int i, int val){
        max[i] = val;
        up[i] = val;
        check[i] = true;
    }
    static int query(int leftJ, int rightJ, int left, int right, int i){
        if(leftJ <= left && right <= rightJ){
            return max[i];
        }
        int ans = Integer.MIN_VALUE;
        int mid = (left + right) / 2;
        down(i, mid - left + 1, right - mid);
        if(leftJ <= mid){
            ans = Math.max(query(leftJ, rightJ, left, mid, i << 1), ans);
        }
        if(rightJ > mid){
            ans = Math.max(query(leftJ, rightJ, mid + 1, right, i << 1 | 1), ans);
        }
        return ans;
    }
    static void update(int leftJ, int rightJ, int value, int left, int right, int i){
        if(leftJ <= left && right <= rightJ){
            lazy(i, value);
        }else{
            int mid = (left + right) / 2;
            down(i, mid - left + 1, right - mid);
            if(leftJ <= mid){
                update(leftJ, rightJ, value, left, mid, i << 1);
            }
            if(rightJ > mid){
                update(leftJ, rightJ, value, mid + 1, right, i << 1 | 1);
            }
            max[i] = Math.max(max[i << 1], max[i << 1 | 1]);
        }
    }
}
